package algorithms.leaning.class19;

import common.util.MyUtil;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个字符串str，给定一个字符串类型的数组arr，出现的字符都是小写英文
 * arr每一个字符串，代表一张贴纸，你可以把单个字符剪开使用，目的是拼出str来
 * 返回需要至少多少张贴纸可以完成这个任务。
 * 例子：str= "babac"，arr = {"ba","c","abcd"}
 * ba + ba + c = 3
 * abcd + abcd = 2
 * abcd + ba = 2
 * 所以返回2
 *
 * @author guichang
 * @date 2021/6/19
 */

@SuppressWarnings("all")
public class Code3_动态规划_贴纸匹配字符串 {

    public static void main(String[] args) {
        String str = "abcd";
        String[] papers = {"ab", "bc", "z", "d"};
        MyUtil.print(papers(papers, str));
    }

    public static int papers(String[] papers, String str) {
        // 边界
        if (papers == null || papers.length == 0 || str == null || str.length() == 0) {
            return -1;
        }
        Map<String, Integer> dp = new HashMap<>();
        int ans = process(papers, str, dp);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    /**
     * 最少需要多少张纸才能将str匹配满
     *
     * @param array  纸张列表
     * @param target 待匹配字符串
     * @return 最少张数
     */
    public static int process(String[] array, String target, Map<String, Integer> dp) {
        if (dp.get(target) != null) {
            return dp.get(target);
        }
        // base case 不用匹配了
        if (target.length() == 0) {
            return 0;
        }
        int ans = Integer.MAX_VALUE;
        for (String a : array) {
            String rest = subtract(target, a);
            // 能匹配上某个字符则继续，否则直接返回
            if (target.length() > rest.length()) {
                ans = Math.min(ans, process(array, rest, dp));
            }
        }
        ans = ans != Integer.MAX_VALUE ? (1 + ans) : ans;
        dp.put(target, ans);
        return ans;
    }

    /**
     * str中间去掉与a公共的字符
     */
    private static String subtract(String str, String a) {
        StringBuilder sb = new StringBuilder(str);
        for (char c : a.toCharArray()) {
            int i = sb.indexOf(String.valueOf(c));
            if (i != -1) {
                sb.deleteCharAt(i);
            }
        }
        return sb.toString();
    }

}